package junior.图;

public class 所有路径_树 {
    static int[][] check = {{1 ,0 ,0 ,0 ,0 , 0},
                            {2 ,3 ,0 ,0 ,0 , 0},
                            {4 ,5 ,1 ,0 ,0 , 0},
                            {7 ,8 ,9 ,10,0 , 0},
                            {11,12,13,14,15, 0},
                            {16,17,18,19,20,21}};
    static int[][] direction = {{1,0},{1,1}}; //下 右 对应 x行，y列
    static int[] result = new int[6];
    static int[] resultPath = new int[6];
    static int n = 6,count = 0,maxPath = 0;
    public static void main(String[] args) {
        recurision(0,0);
        System.out.println("总方案数为：" + count);
        System.out.println("路径最大值：" + maxPath);
        System.out.print("最大值路径：");
        for (int i = 0; i <n; i++) {
            System.out.print(resultPath[i]+" ");
        }
    }
    static void recurision(int x,int y){  // x 行 ， y 列
        int newX,newY;
        result[x] = check[x][y];
        // 结束条件
        if(x == n-1 || y == n-1){
            int sum = 0;
            System.out.println("方案 "+(count+1)+" :***********************");
            for (int i = 0; i < n; i++) {
                sum += result[i];
                System.out.print(result[i]+" ");
            }
            if(sum > maxPath){
                maxPath = sum;
                for (int i = 0; i < n; i++) {
                    resultPath[i] = result[i];
                }
            }
            System.out.println();
            count++;
            return;
        }
        // 深度优先搜索
        for (int i = 0; i < 2; i++) { // 遍历2个方向
            newX = x+direction[i][0];
            newY = y+direction[i][1];
            if( 0<=newX && newX< n && 0<=newY && newY<n){ // 判断：边界，是否为1（强）
                recurision(newX,newY); // 递归
            }
        }
    }
}
